import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author VernHe
 * @date 2021年06月22日 13:07
 */
public class Solution_0234 {
    public boolean isPalindrome(ListNode head) {
        if (null == head) {
            return true;
        }
        // 找打中间位置
        ListNode mid = findMid(head);
        // 反转后面的内容
        ListNode secondHalfStart = reverse(mid.next);

        // 判断回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        while (p2 != null) {
            if (p1.val != p2.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }

    /**
     * 翻转链表
     * @param head
     * @return
     */
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode tempNode = null;
        while (null != cur) {
            tempNode = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tempNode;
        }
        return pre;
    }

    /**
     * 找到中间位置
     * @param head
     * @return
     */
    private ListNode findMid(ListNode head) {
        ListNode slow = head,fast = head;
        while (null != fast.next && null != fast.next.next) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public boolean isPalindrome1(ListNode head) {
        Deque<ListNode> deque = new ArrayDeque<>();
        ListNode node = head.next;
        deque.add(head);
        while (null != node) {
            deque.add(node);
            node = node.next;
        }
        ListNode first,last;
        while (!deque.isEmpty()) {
            if (deque.size() < 2) {
                return true;
            }
            last = deque.removeLast();
            first = deque.removeFirst();
            if (first.val != last.val) {
                return false;
            }
        }
        return true;
    }
}
